package zhoujian.oj.leetcode;


/**
 * @author hyper
 * @email zjkermit@gmail.com
 * @date 2013-12-4
 * @version 1.0
 */
public class MedianOfTwoSortedArrays {
	
	public static double findKthSmallest(int A[], int m, int B[], int n, int k){  
        int ia = 0, ib = 0, res = 0;  
        while(k >= 0 && ia < m && ib < n){  
            if(A[ia] < B[ib])  
                res = A[ia++];  
            else  
                res = B[ib++];  
            k--;
        }  
        while(ia < m && k >=0) {  
            res = A[ia++];  
            k--;
        }
        while(ib < n && k >=0) {  
            res = B[ib++];  
            k--;
        }
        return res;  
    }  

	public static double findMedianSortedArrays(int A[], int B[]) {
		int m = A.length, n = B.length;  
        if ((m + n) % 2 == 0)
            return (findKthSmallest(A, m , B, n, (m + n - 1) / 2 + 1) + findKthSmallest(A, m , B, n, (m + n - 1) / 2)) / 2.0;  
        else
            return findKthSmallest(A, m , B, n, (m + n - 1) / 2);  
	}

	public static void main(String[] args) {
		int[] A = new int[] { 0, 1, 3 };
		int[] B = new int[] { 4, 5, 6, 7, 8 };
		System.out.println(findMedianSortedArrays(A, B));
	
		A = new int[0];
		B = new int[] { 4 };
		System.out.println(findMedianSortedArrays(A, B));
		
		A = new int[] { 2 };
		B = new int[] { };
		System.out.println(findMedianSortedArrays(A, B));
		
		A = new int[] {};
		B = new int[] { 2, 3 };
		System.out.println(findMedianSortedArrays(A, B));
		
		A = new int[] { 100000 };
		B = new int[] { 100001 };
		System.out.println(findMedianSortedArrays(A, B));
		
		A = new int[] { 3,6,7,8,9,10 };
		B = new int[] { 1,2,4,5 };
		System.out.println(findMedianSortedArrays(A, B));
	}

}
